package leecode.array;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author wangxi created on 2021/5/29 18:00
 * @version v1.0
 *
 * https://leetcode-cn.com/problems/sliding-window-maximum/
 * 可参照官方题解 第一种解法
 */
public class MaxInWindows {

    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length <= 0 || k <= 0) {
            return new int[0];
        }
        List<Integer> list = new ArrayList<>();
        // index - num
        PriorityQueue<int[]> queue = new PriorityQueue<>(
                (o1, o2) -> Integer.compare(o2[1], o1[1]));
        int i = 0;
        for (; i < k; i++) {
            int[] item = {i, nums[i]};
            queue.offer(item);
        }
        list.add(queue.peek()[1]);
        for (; i < nums.length; i++) {
            int[] item = {i, nums[i]};
            queue.add(item);
            while (i - queue.peek()[0] >= k) {
                queue.poll();
            }
            list.add(queue.peek()[1]);
        }
        int[] res = new int[list.size()];
        for (int j = 0; j < res.length; j++) {
            res[j] = list.get(j);
        }
        return res;
    }
}
